#ifndef BTREE_H
#define BTREE_H

#ifndef NULL
#define NULL 0
#endif

template<typename T>
class BTree {
    protected:
        BTree *left;
        BTree *right;
        BTree *p;
        T _elt;
        unsigned height;
        bool NiL;

    public:
        BTree() : NiL(true), left(NULL), right(NULL), p(NULL), height(0) {}
        BTree(T e, BTree *l = NULL, BTree *r = NULL, BTree *p = NULL)
            : _elt(e), left(l), right(r), p(p), height(1)
            {NiL = false;}
        virtual ~BTree() {
            if(left)
                delete left;
            if(right)
                delete right;
        }

        bool empty () { return NiL; }
        bool isLeaf () { return (left || right); }
        const T& Root () { return _elt; }
        BTree<T> *Left() { return left; }
        BTree<T> *Right() { return right; }
        BTree<T> *Parent() { return p; }
};

#endif /* BTREE_H */
